import java.util.LinkedList;
import java.util.Queue;

// 二叉树练习
public class MyBinaryTree {
    class TreeNode {
        //1.建立数据域、左孩子的引用和右孩子的引用
        public char val; // 数据域
        public TreeNode left;//存储左孩子的引用
        public TreeNode right;//存储右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }

    // 开始创建二叉树
    public TreeNode createThree() {
        TreeNode treeNodeA = new TreeNode('A');
        TreeNode treeNodeB = new TreeNode('B');
        TreeNode treeNodeC = new TreeNode('C');
        TreeNode treeNodeD = new TreeNode('D');
        TreeNode treeNodeE = new TreeNode('E');
        TreeNode treeNodeF = new TreeNode('F');
        TreeNode treeNodeG = new TreeNode('G');
        TreeNode treeNodeH = new TreeNode('H');

        // 有左孩子赋值到左边，右孩子赋值到右边
        treeNodeA.left = treeNodeB;
        treeNodeB.left = treeNodeD;
        treeNodeB.right = treeNodeE;
        treeNodeE.right = treeNodeH;
        treeNodeA.right = treeNodeC;
        treeNodeC.left = treeNodeF;
        treeNodeC.right = treeNodeG;
        return treeNodeA;//确定根节点
    }

    // 实现前序遍历
    public void preOrder(TreeNode root) {
        // 树为空
        if (root == null) {
            return;
        }
        System.out.println("root:"+ root.val);
        // 递归左右的树
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    public void inOrder(TreeNode root) {
        // 树为空
        if (root == null) {
            return;
        }
        preOrder(root.left);
        System.out.println("root:"+ root.val);
        preOrder(root.right);
    }

    // 后序遍历
    public void postOrder(TreeNode root) {
        // 树为空
        if (root == null) {
            return;
        }
        preOrder(root.left);
        preOrder(root.right);
        System.out.println("root:"+ root.val);
    }

    // 遍历求树的结点个数
    public static int nodeSize = 0; // 计数器
    public int size(TreeNode root) {
        if (root == null) {
            // 为空则没有结点
            return 0;
        }
        // 不为空时先计算上 root 结点
        nodeSize++;
        size(root.left);
        size(root.right);
        return nodeSize;
    }

    // 递归求节点个数
    public int getNodeSize(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getNodeSize(root.left) + getNodeSize(root.right) + 1; // 左树右树加 root 结点
    }

    // 遍历求叶子节点个数
    public static int leafSize = 0;//叶子计数器
    public int getLeafNodeCount(TreeNode root) {
        if (root == null) {
            //  树为空则没有叶子结点
            return 0;
        }
        if (root.left == null && root.right == null) {
            leafSize++;
        }
        // 调用方法找左右的孩子
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return leafSize;
    }

    // 递归求叶子节点个数
    public int leafNodeSize(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;//叶子结点个数
        }
        return leafNodeSize(root.left) + leafNodeSize(root.right); // 返回两边的叶子节点和
    }

    //递归实现获取第k层的节点个数
    public int getKLevelNodeCount(TreeNode root, int k) {
        // 如果是第一层直接返回1
        if (k == 2) {
            return 1;
        }
        if (root == null || k <= 0) {
            return 0;
        }
        return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
    }

    //递归实现获取二叉树的高度
    public int getHeight(TreeNode root) {
        //为空
        if (root == null) {
            return 0;
        }
        //不为空
        int leftHeight = getHeight(root.left);//求左树的高度
        int rightHeight = getHeight(root.right);//求右树的高度
        //返回左右树的最大值加1
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    //递归查找val值是否存在
    public TreeNode findVal(TreeNode root, char val) {
        //为空
        if (root == null) {
            return null;
        }
        //不为空的情况
        //根节点此时的值等于我要查找的值
        if (root.val == val) {
            //返回此时root的地址
            return root;
        }
        //root此时的值不等于我要查找的值 - 调用方法访问左右两边的值
        TreeNode leftVal = findVal(root.left, val);//访问左边
        //此时左边的值不为空就继续找
        if (leftVal != null) {
            return leftVal;
        }
        TreeNode rightVal = findVal(root.right, val);//访问右边
        //此时右边的值不为空就继续找
        if (rightVal != null) {
            return rightVal;
        }
        //整个树都访问完了就说明没有val值
        return null;
    }

    //非递归实现层序遍历
    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //不为空 - 实现队列
        Queue<TreeNode> queue = new LinkedList<>();
        //压入元素到队列中
        queue.offer(root);
        //队列不为空
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();//弹出给cur
            //同时打印队头的元素
            System.out.print(cur.val + " ");
            //如果cur的左边不是空的说明未遍历结束
            if (cur.left != null) {
                //继续压入元素到队列中
                queue.offer(cur.left);
            }
            //如果cur右边不是空的说明未遍历结束
            if (cur.right != null) {
                //继续压入
                queue.offer(cur.right);
            }
        }
    }

    //非递归实现层序遍历
    public void levelOrders(TreeNode root) {
        if (root == null) {
            return;
        }
        //不为空 - 实现队列
        Queue<TreeNode> queue = new LinkedList<>();
        //压入元素到队列中
        queue.offer(root);
        //队列不为空
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();//弹出给cur
            //同时打印队头的元素
            System.out.print(cur.val + " ");
            //如果cur的左边不是空的说明未遍历结束
            if (cur.left != null) {
                //继续压入元素到队列中
                queue.offer(cur.left);
            }
            //如果cur右边不是空的说明未遍历结束
            if (cur.right != null) {
                //继续压入
                queue.offer(cur.right);
            }
        }
    }

    //判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        //为空的情况
        if (root == null) {
            return true;//是完全二叉树
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//将此时root结点放到队列中
        //队列不为空
        while (!queue.isEmpty()) {
            //弹出此时队列的队头元素
            TreeNode cur = queue.poll();
            //压入root的左和右
            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        //判断队列剩下的值是否有非null的数据
        while (!queue.isEmpty()) {
            TreeNode popValue = queue.poll();//弹出此时队头的元素
            //如果队列中有非null的元素则不是完全二叉树
            if (popValue != null) {
                return false;
            }
        }
        //若循环结束说明都为空 - 即是完全二叉树
        return true;
    }

    public static void main(String[] args) {

    }
}
